# -*- coding: utf-8 -*-

# 实现 int sqrt(int x) 函数
# 计算并返回 x 的平方根，其中 x 是非负整数
# 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去

# 示例 1:
# 输入: 4
# 输出: 2

# 示例 2:
# 输入: 8
# 输出: 2
# 说明: 8 的平方根是 2.82842..., 
#      由于返回类型是整数，小数部分将被舍去。




# 使用牛顿迭代法进行求解
# 牛顿迭代法：
# 假设要开方的数字为n
# 可得方程f(x) = pow(x, 2) - n;
# 当f(x) == 0时，x的值即为n的平方根
# 
# 1、 使用f(1)来判断是否是平方根，如果不是则从点(1, f(1))开始做切线，切线与x轴的交点为a
# 2、 判断f(a)是否是平方根，如果不是则从点(a, f(a))开始做切线，切线与x轴的交点为b
# ......
# 重复以上步骤则逐渐向结果逼近
# 
# 通过以上算法的过程可知，关键在于计算f(x)的切线与x轴的交点
# 点 (m, f(m)) => (m, pow(m, 2) - n)
# 切线方程 
#   g(x) = 2*m*(x - m) + pow(m, 2) - n;
# =>g(x) = 2*m*x - 2*m*m + m*m - n;
# =>g(x) = 2*m*x -m*m - n;
# 与x轴的交点为
# 0 = 2*m*x - m*m - n
# 2*mx = m*m + n
# x = (m + n / m) / 2

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        last = 0;
        rtn = 1;
        while abs(rtn - last) > 0.1:
            print abs(rtn - last);
            last = rtn;
            rtn = (rtn + x / rtn) / 2.0;
        return int(rtn);

t = Solution();
print t.mySqrt(10010);